package club.xiaojiawei.binarytree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/13/22 12:28 AM
 * @question 101. 对称二叉树
 * @description 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 */
public class IsSymmetric101 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(2);
        left.left = new TreeNode(3);
        left.right = new TreeNode(4);
        right.left = new TreeNode(4);
        right.right = new TreeNode(3);
        root.left = left;
        root.right = right;
        boolean result = isSymmetric(root);
        System.out.println(result);
    }

    /**
     * BFS+双向队列
     * @param root
     * @return
     */
    public static boolean isSymmetric(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        if (root.left != null){
            if (root.right == null || root.right.val != root.left.val){
                return false;
            }
            queue.addFirst(root.left);
            queue.addLast(root.right);
        }else if (root.right != null){
            return false;
        }
        int size, index;
        while ((size = queue.size()) > 0){
            if (size % 2 == 1){
                return false;
            }
            index = size >> 1;
            for (int i = 0; i < index; i++) {
                TreeNode left = queue.removeFirst();
                TreeNode right = queue.removeLast();
                if (left.val != right.val){
                    return false;
                }
                if (left.left != null){
                    if (right.right == null){
                        return false;
                    }
                    queue.addFirst(left.left);
                    queue.addLast(right.right);
                }else if (right.right != null){
                    return false;
                }
                if (left.right != null){
                    if (right.left == null){
                        return false;
                    }
                    queue.addFirst(left.right);
                    queue.addLast(right.left);
                }else if (right.left != null){
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 官方-迭代
     * @param root
     * @return
     */
    public static boolean isSymmetric2(TreeNode root) {
        return check(root, root);
    }

    public static boolean check(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
    }

    /**
     * 官方-迭代
     * @param root
     * @return
     */
    public static boolean isSymmetric3(TreeNode root) {
        return check2(root, root);
    }

    public static boolean check2(TreeNode u, TreeNode v) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) {
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) {
                continue;
            }
            if ((u == null || v == null) || (u.val != v.val)) {
                return false;
            }
            q.offer(u.left);
            q.offer(v.right);
            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
